home *** CD-ROM | disk | FTP | other *** search
/ CICA 1995 September (Japanese) / CICA Shareware for Windows CD-ROM (Walnut Creek) (September 1995) (Japanese) (Disc 2).iso / disc2 / programr / atre27.exe / ATREE_27 / INCLUDE / ATREE.C next >
Encoding:
C/C++ Source or Header  |  1992-08-01  |  72.5 KB  |  2,184 lines
  1. /*****************************************************************************
  2.  ****                                                                     ****
  3.  **** atree.c  for Windows                                                ****
  4.  ****                                                                     ****
  5.  **** atree release 2.7                                                   **** 
  6.  **** Adaptive Logic Network (ALN) simulation library.                    ****
  7.  **** Copyright (C) A. Dwelly, R. Manderscheid, M. Thomas, W.W. Armstrong ****
  8.  ****               1991, 1992                                            ****
  9.  ****                                                                     ****
  10.  **** License:                                                            ****
  11.  **** A royalty-free license is granted for the use of this software for  ****
  12.  **** NON_COMMERCIAL PURPOSES ONLY. The software may be copied and/or     ****
  13.  **** modified provided this notice appears in its entirety and unchanged ****
  14.  **** in all derived source programs.  Persons modifying the code are     ****
  15.  **** requested to state the date, the changes made and who made them     ****
  16.  **** in the modification history.                                        ****
  17.  ****                                                                     ****
  18.  **** Patent License:                                                     ****
  19.  **** The use of a digital circuit which transmits a signal indicating    ****
  20.  **** heuristic responsibility is protected by U. S. Patent 3,934,231     ****
  21.  **** and others assigned to Dendronic Decisions Limited of Edmonton,     ****
  22.  **** W. W. Armstrong, President.  A royalty-free license is granted      ****
  23.  **** by the company to use this patent for NON_COMMERCIAL PURPOSES ONLY  ****
  24.  **** to adapt logic trees using this program and its modifications.      ****
  25.  ****                                                                     ****
  26.  **** Limited Warranty:                                                   ****
  27.  **** This software is provided "as is" without warranty of any kind,     ****
  28.  **** either expressed or implied, including, but not limited to, the     ****
  29.  **** implied warrantees of merchantability and fitness for a particular  ****
  30.  **** purpose.  The entire risk as to the quality and performance of the  ****
  31.  **** program is with the user.  Neither the authors, nor the             ****
  32.  **** University of Alberta, its officers, agents, servants or employees  ****
  33.  **** shall be liable or responsible in any way for any damage to         ****
  34.  **** property or direct personal or consequential injury of any nature   ****
  35.  **** whatsoever that may be suffered or sustained by any licensee, user  ****
  36.  **** or any other party as a consequence of the use or disposition of    ****
  37.  **** this software.                                                      ****
  38.  ****                                                                     ****
  39.  **** Modification history:                                               ****
  40.  ****                                                                     ****
  41.  **** 90.05.09 Initial implementation, A.Dwelly                           ****
  42.  **** 91.07.15 Release 2, Rolf Manderscheid                               ****
  43.  ****          Thanks to Allen Supynuk for turning my compression         ****
  44.  ****          function into something readable.                          ****
  45.  **** 91.10.30 0.0 and 1.0 replaced by code -> low and code -> high in    ****
  46.  ****          atree_read_code to correct bug found by Monroe Thomas      ****
  47.  **** 92.27.02 Release 2.5, Monroe Thomas                                 ****
  48.  **** 92.03.07 Release 2.6, Monroe Thomas                                 ****
  49.  **** 92.01.08 Release 2.7, Monroe Thomas                                 ****
  50.  ****                                                                     ****
  51.  *****************************************************************************/
  52.  
  53. /*****************************************************************************
  54.  ****                                                                     ****
  55.  **** Include Files                                                       ****
  56.  ****                                                                     ****
  57.  *****************************************************************************/
  58.  
  59. #include <windows.h>
  60. #include <time.h>
  61.  
  62. #ifndef __ATREE_H
  63. #include "atree.h"
  64. #endif
  65.  
  66. extern int errno;
  67.  
  68. /*****************************************************************************
  69.  ****                                                                     ****
  70.  **** Constants                                                           ****
  71.  ****                                                                     ****
  72.  *****************************************************************************/
  73.  
  74. /* Node and leaf types */
  75.  
  76. #define AND 0
  77. #define RIGHT 1
  78. #define LEFT 2
  79. #define OR 3
  80. #define LEAF 4
  81.  
  82. #define LEFT_CHILD 0
  83. #define RIGHT_CHILD 1
  84.  
  85. #define FALSE 0           /* As usual */
  86. #define TRUE 1
  87. #define UNEVALUATED 2     /* We complete the lattice of boolean functions */
  88. #define ATREE_ERROR 3
  89.  
  90. /* Number of retries before an error in atree_rand_walk */
  91. #define MAX_RETRY 50
  92.  
  93. /* Number of nodes/leaves to allocate in each call to malloc in get_node() */
  94. #define NEWMALLOC   1024
  95.  
  96. /* Initialisation values */
  97.  
  98. #define MAXSET      63
  99. #define ABOVEMID    32
  100. #define BELOWMID    31
  101. #define MINSET      0
  102.  
  103.  
  104. #define STACKSIZE   100     /* stack used in load_tree */
  105. #define LEAF_TOKEN 256
  106.  
  107. #define CODING_HEADER_FORMAT    "vectors=%i, width=%i, range=%f,%f\n"
  108. #define CODING_HEADER_ITEMS     4
  109.  
  110. /*
  111.  * Macros
  112.  */
  113.  
  114. /* This keeps lint quiet */
  115.  
  116. #define Printf (void) printf
  117.  
  118. /* Public and private procedures */
  119.  
  120. #define public
  121. #define private static
  122.  
  123. /* Infinite loops - for EVER */
  124.  
  125. #define EVER (;;)
  126.  
  127. /* Printing out the boolean lattice */
  128.  
  129. #define PRINTBOOL(b) if (b == TRUE) {Printf("1");} else if (b == FALSE)\
  130.     {Printf("0");} else if (b == UNEVALUATED) {Printf("U");} else \
  131.     if (b == ATREE_ERROR) {Printf("E");} else {Printf("?");}
  132.  
  133. /* Verbosity */
  134.  
  135. #define VERBOSE(level,s) if (verbosity >= level) {s ;}
  136.  
  137. /*
  138.  * Types
  139.  */
  140.  
  141. typedef struct token_struct
  142. {
  143.     int token;
  144.     int bit_no;
  145.     int complemented;
  146. } token_t;                  // struct is 6 bytes long
  147.  
  148. /*
  149.  * Preliminary Private Procedure Declarations
  150.  */
  151.  
  152. private LPATREE NEAR PASCAL     get_node(int);
  153. private void NEAR PASCAL        reclaim_node(LPATREE);
  154. private LPATREE NEAR PASCAL     build_tree(LPINT, BOOL far *,int,int);
  155. private void NEAR PASCAL        print_tree(LPATREE, FILE *, int, int);
  156. private BOOL NEAR PASCAL        train(LPATREE, LPBIT_VEC, BOOL);
  157. private void NEAR PASCAL        adapt(LPATREE, LPBIT_VEC, BOOL);
  158. private int NEAR PASCAL         node_function(LPATREE);
  159. private void NEAR PASCAL        compress_tree(LPATREE,LPFAST_TREE,LPFAST_TREE,LPFAST_TREE,LPINT);
  160. private int NEAR PASCAL         count_leaves(LPATREE, int);
  161. private int NEAR PASCAL         store_tree(LPATREE, FILE *);
  162. private int NEAR PASCAL         get_token(FILE *, token_t far *);
  163.  
  164.  
  165. BOOL atree_quit_flag;
  166.  
  167. HWND hStatusWnd;
  168.  
  169. #pragma argsused
  170. long FAR PASCAL StatusDlgProc(HWND hwnd, WORD message, WORD wParam, LONG lParam)
  171. {
  172.     if ((message == WM_COMMAND) && (wParam == IDCANCEL))
  173.     {
  174.         atree_quit_flag = TRUE;
  175.         return(TRUE);
  176.     }
  177.     return(FALSE);
  178. }
  179.  
  180. /*****************************************************************************
  181.  *****************************************************************************
  182.  ****                                                                     ****
  183.  ****                        Public Routines                              ****
  184.  ****                                                                     ****
  185.  *****************************************************************************
  186.  *****************************************************************************/
  187.  
  188. /*****************************************************************************
  189.  ****                                                                     ****
  190.  **** void FAR PASCAL Windows_Interrupt(cElapsed)                         ****
  191.  ****                                                                     ****
  192.  **** DWORD cElapsed                                                      ****
  193.  ****                                                                     ****
  194.  **** Synopsis:                                                           ****
  195.  ****                                                                     ****
  196.  **** Allows Windows to access other applications that may be running     ****
  197.  **** A call to PeekMessage accomplishes this, and we process all calling ****
  198.  **** window messages. Will only call PeekMessage if _cElapsed_ time      ****
  199.  **** has passed since the last call to Windows_Interrupt.                ****
  200.  ****                                                                     ****
  201.  *****************************************************************************/
  202.  
  203. public void FAR PASCAL
  204. Windows_Interrupt(cElapsed)
  205.  
  206. DWORD cElapsed;
  207.  
  208. {
  209.     static DWORD    cTick = 0;      /* number of ticks since first called */
  210.     MSG             msg;            /* Windows message structure */
  211.  
  212.     if ((GetTickCount() - cTick) > cElapsed)
  213.         {
  214.         if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))
  215.             {
  216.             TranslateMessage(&msg);
  217.             DispatchMessage(&msg);
  218.             }
  219.         cTick = GetTickCount();
  220.         }
  221. }
  222.  
  223.  
  224. /*****************************************************************************
  225.  ****                                                                     ****
  226.  **** void atree_init(hInstance, hWindow)                                 ****
  227.  ****                                                                     ****
  228.  **** HANDLE hInstance;                                                   ****
  229.  ****                                                                     ****
  230.  **** Synopsis:                                                           ****
  231.  ****                                                                     ****
  232.  **** Initialises various global variables, and makes an initial call to  ****
  233.  **** the random number seed routine.                                     ****
  234.  *****************************************************************************/
  235.  
  236. public void FAR PASCAL
  237. atree_init(hInstance, hWindow)
  238.  
  239. HANDLE hInstance;
  240. HWND hWindow;
  241. {
  242.     DWORD c;
  243.  
  244. #pragma warn -nod
  245.     randomize();
  246. #pragma warn .nod
  247.     c = GetTickCount();
  248.     (void) srand((int) c);
  249.  
  250.     c = GetWinFlags();
  251.     if (!(c & WF_PMODE))
  252.     {
  253.         MessageBox(hWindow, "Atree software cannot run\nin Windows Real Mode!",
  254.                    "Not in Protected Mode!", MB_OK | MB_ICONSTOP);
  255.         exit(0);
  256.     }
  257.  
  258.     hStatusWnd = CreateDialog(hInstance, "atreeStatus", hWindow,
  259.                                  MakeProcInstance((FARPROC)StatusDlgProc, hInstance));
  260.  
  261.     atree_quit_flag = FALSE;
  262.     return;
  263. }
  264.  
  265. /*****************************************************************************
  266.  ****                                                                     ****
  267.  **** void atree_quit()                                                   ****
  268.  ****                                                                     ****
  269.  **** sets the quit flag for use by other atree routines when an exit     ****
  270.  **** is desired                                                          ****
  271.  *****************************************************************************/
  272.  
  273. void FAR PASCAL
  274. atree_quit(void)
  275.  
  276. {
  277.     atree_quit_flag = TRUE;
  278.     if (IsWindow(hStatusWnd))
  279.     {
  280.         DestroyWindow(hStatusWnd);
  281.     }
  282. }
  283.  
  284.  
  285. /*****************************************************************************
  286.  ****                                                                     ****
  287.  **** LPBIT_VEC atree_rand_walk(num,width,p)                              ****
  288.  ****                                                                     ****
  289.  **** int num;                                                            ****
  290.  **** int width;                                                          ****
  291.  **** int p;                                                              ****
  292.  ****                                                                     ****
  293.  **** Synopsis:                                                           ****
  294.  ****                                                                     ****
  295.  **** Creates an array of _num_ binary vectors, of _width_ bits where     ****
  296.  **** each is _p_ bits away from its neighbours in Hamming space. Each    ****
  297.  **** vector is unique.                                                   ****
  298.  **** This routine returns NULL if it's unable to find enough vectors.    ****
  299.  *****************************************************************************/
  300.  
  301. public LPBIT_VEC FAR PASCAL
  302. atree_rand_walk(num,width,p)
  303.  
  304. int num;
  305. int width;
  306. int p;
  307.  
  308. {
  309.     /*
  310.      * An initial vector is produced with random bits, and each subsequent
  311.      * vector in the random walk just has _p_ bits flipped. In order to
  312.      * guarantee that each vector is unique, it is checked against
  313.      * a chained list of vectors of the same bit sum. If it is not already
  314.      * in the chain it is appended to the end, or else the vector is discarded
  315.      * and the process repeats itself.
  316.      */
  317.  
  318.     LPBIT_VEC walk;             /* An array of bit vectors */
  319.     LPBIT_VEC pckd_vec;         /* The packed unique ? vector */
  320.     BOOL unique;                /* Uniqueness flag set during testing */
  321.     LPINT bit_sum_chain;        /* Pointers to vectors of equivalent bit sums */
  322.     LPINT next_vec;             /* Chain array */
  323.     LPSTR unpckd_vec;           /* An unpacked vector */
  324.     LPSTR this_vec;             /* An unpacked vector */
  325.     LPSTR mark_vec;             /* TRUE where a bit has been flipped */
  326.     int i;
  327.     int j;
  328.     int old_bit_sum;            /* Last number of TRUE bits in vector */
  329.     int bit_sum;                /* Current number of TRUE bits in vector */
  330.     int retrys;                 /* Number of attempts to find a unique vec */
  331.     int victim;                 /* The bit just twiddled */
  332.     int current_vec;            /* Part of the chain */
  333.  
  334.     assert(num > 0);
  335.     assert(width > 0);
  336.     assert(p > 0 && p <= width);
  337.  
  338.     /* Assign space in memory */
  339.  
  340.     walk = (LPBIT_VEC ) farmalloc((unsigned) num * sizeof(bit_vec));
  341.     MEMCHECK(walk);
  342.     bit_sum_chain = (LPINT) farmalloc((unsigned) (width+1) * sizeof(int));
  343.     MEMCHECK(bit_sum_chain);
  344.     next_vec = (LPINT) farmalloc((unsigned) num * sizeof(int));
  345.     MEMCHECK(next_vec);
  346.     unpckd_vec = (LPSTR) farmalloc((unsigned) width * sizeof(char));
  347.     MEMCHECK(unpckd_vec);
  348.     this_vec = (LPSTR) farmalloc((unsigned) width * sizeof(char));
  349.     MEMCHECK(this_vec);
  350.     mark_vec = (LPSTR) farmalloc((unsigned) width * sizeof(char));
  351.     MEMCHECK(mark_vec);
  352.  
  353.     /* Clear bit_sum_chain */
  354.  
  355.     for (i = 0; i <= width; i++)
  356.     {
  357.         bit_sum_chain[i] = -1;
  358.     }
  359.  
  360.     /* Clear next_vec */
  361.  
  362.     for (i = 0; i < num; i++)
  363.     {
  364.         next_vec[i] = -1;
  365.     }
  366.  
  367.     /* Create initial vector and bit sum */
  368.  
  369.     old_bit_sum = 0;
  370.     for (i = 0; i < width; i++)
  371.     {
  372. // turn off compiler possibly incorrect assignment warning
  373. #pragma warn -pia
  374.         if (unpckd_vec[i] = RANDOM(2))
  375.         {
  376.            old_bit_sum++;
  377.         }
  378. // restore warning state
  379. #pragma warn .pia
  380.     }
  381.  
  382.     walk[0] = *(bv_pack(unpckd_vec,width));
  383.     bit_sum_chain[old_bit_sum] = 0;
  384.  
  385.     /* Random walk */
  386.  
  387.     for (i = 1; i < num; i++)
  388.     {
  389.         retrys = 0;
  390.         unique = FALSE;
  391.         while ((!unique) && (retrys < MAX_RETRY))
  392.         {
  393.             retrys++;
  394.  
  395.             /* Make a new vector */
  396.  
  397.             bit_sum = old_bit_sum;
  398.             for (j = 0; j < width; j++)
  399.             {
  400.                 this_vec[j] = unpckd_vec[j];
  401.                 mark_vec[j] = FALSE;
  402.             }
  403.  
  404.             for (j = 0; j < p; j++)
  405.             {
  406.                 do
  407.                 {
  408.                     victim = RANDOM(width);
  409.                 }
  410.                 while (mark_vec[victim]);
  411.  
  412.                 mark_vec[victim] = TRUE;
  413.                 this_vec[victim] = !this_vec[victim];
  414.                 if (this_vec[victim] == FALSE)
  415.                 {
  416.                     bit_sum--;
  417.                 }
  418.                 else
  419.                 {
  420.                     bit_sum++;
  421.                 }
  422.             }
  423.  
  424.             pckd_vec = bv_pack(this_vec,width);
  425.  
  426.             /* Compare it with the existing ones of equal bit length */
  427.  
  428.             if (bit_sum_chain[bit_sum] == -1)
  429.             {
  430.                 /* There are no other vectors with this bit sum, so */
  431.  
  432.                 unique = TRUE;
  433.                 walk[i] = *pckd_vec;
  434.                 bit_sum_chain[bit_sum] = i;
  435.                 next_vec[i] = -1;
  436.             }
  437.             else
  438.             {
  439.                 current_vec = bit_sum_chain[bit_sum];
  440.                 for EVER /* We break out of here inside the loop */
  441.                 {
  442.                     if (bv_equal(&(walk[current_vec]),pckd_vec))
  443.                     {
  444.                         /* This vector already exists,  unique = FALSE; */
  445.                         break;
  446.                     }
  447.                     else
  448.                     {
  449.                         if (next_vec[current_vec] == -1)
  450.                         {
  451.                             unique = TRUE;
  452.                             walk[i] = *pckd_vec;
  453.                             next_vec[current_vec] = i;
  454.                             next_vec[i] = -1;
  455.                             break;
  456.                         }
  457.                         else
  458.                         {
  459.                             current_vec = next_vec[current_vec];
  460.                         }
  461.                     }
  462.                 } /* for EVER */
  463.             } /* if (bit_sum_chain...) */
  464.         } /* while ((!unique... ))*/
  465.  
  466.         /*
  467.          * If Unique is TRUE at this point, we have a unique
  468.          * vector stored, we have to set up old_bit sum and unpckd_vec
  469.          * for the next vector.
  470.          * If unique is FALSE, we have tried to create a unique vector
  471.          * MAX_RETRY times, and failed. We therefore signal an error.
  472.          */
  473.  
  474.         if (unique)
  475.         {
  476.             for (j = 0; j < width; j++)
  477.             {
  478.                 unpckd_vec[j] = this_vec[j];
  479.             }
  480.             old_bit_sum = bit_sum;
  481.         }
  482.         else
  483.         {
  484.             (void) farfree(walk);
  485.             walk = NULL;
  486.             break;
  487.         }
  488.     } /* for */
  489.  
  490.  
  491.     /* Free space in memory */
  492.  
  493.     (void) farfree(bit_sum_chain);
  494.     (void) farfree(next_vec);
  495.     (void) farfree(unpckd_vec);
  496.     (void) farfree(this_vec);
  497.     (void) farfree(mark_vec);
  498.  
  499.     /* Return final vector */
  500.  
  501.     return(walk);
  502. }
  503.  
  504. /*****************************************************************************
  505.  ****                                                                     ****
  506.  **** LPATREE atree_create(numvars,leaves)                                ****
  507.  ****                                                                     ****
  508.  **** int numvars;                                                        ****
  509.  **** int leaves;                                                         ****
  510.  ****                                                                     ****
  511.  **** Synopsis:                                                           ****
  512.  ****                                                                     ****
  513.  **** Creates an Armstrong tree with _leaves_ number of leaves connected  ****
  514.  **** to _numvars_  variables and their complements.  The number of       ****
  515.  **** leaves should probably be at least twice _numvars_.                 ****
  516.  **** The node functions and the connections are picked at random.        ****
  517.  ****                                                                     ****
  518.  *****************************************************************************/
  519.  
  520. public LPATREE FAR PASCAL
  521. atree_create(numvars,leaves)
  522.  
  523. int numvars;
  524. int leaves;
  525.  
  526. {
  527.     LPATREE tree;
  528.     LPINT connection;
  529.     BOOL far *complemented;
  530.     BOOL comp;
  531.     int i;
  532.  
  533.     assert(leaves > 0);
  534.     assert(numvars > 0);
  535.  
  536.     /*
  537.      * Create a list of bit inputs and shuffle, complemented inputs
  538.      * are marked with a TRUE in the complemented array.
  539.      */
  540.  
  541.     connection = (LPINT) farmalloc((unsigned) sizeof(int) * leaves);
  542.     MEMCHECK(connection);
  543.     complemented = (BOOL far *) farmalloc((unsigned) sizeof(BOOL) * leaves);
  544.     MEMCHECK(complemented);
  545.  
  546.     comp = FALSE;
  547.     for (i = 0; i < leaves; i++)
  548.     {
  549.         int numvarscount = i % numvars;
  550.         if (numvarscount == 0)
  551.         {
  552.             comp = !comp;
  553.         }
  554.         connection[i] = numvarscount;
  555.         complemented[i] = comp;
  556.     }
  557.  
  558.     /* Shuffle */
  559.  
  560.     for (i = 0; i < leaves; i++)
  561.     {
  562.         int a;
  563.         int b;
  564.         int tmp;
  565.  
  566.         a = RANDOM(leaves);
  567.         b = RANDOM(leaves);
  568.         tmp = connection[a];
  569.         connection[a] = connection[b];
  570.         connection[b] = tmp;
  571.         tmp = complemented[a];
  572.         complemented[a] = complemented[b];
  573.         complemented[b] = tmp;
  574.     }
  575.  
  576.     tree = build_tree(connection, complemented, 0, leaves - 1);
  577.  
  578.     (void) farfree(connection);
  579.     (void) farfree(complemented);
  580.  
  581.     return(tree);
  582. }
  583.  
  584. /*****************************************************************************
  585.  ****                                                                     ****
  586.  **** void atree_free(tree)                                               ****
  587.  ****                                                                     ****
  588.  **** LPATREE tree;                                                       ****
  589.  ****                                                                     ****
  590.  **** Synopsis:                                                           ****
  591.  ****                                                                     ****
  592.  **** Returns memory occupied by _tree_ to the freelists.                 ****
  593.  *****************************************************************************/
  594.  
  595. public void FAR PASCAL
  596. atree_free(tree)
  597. LPATREE tree;
  598. {
  599.     if (tree -> c_tag != LEAF)
  600.     {
  601.         atree_free(tree -> n_child_left);
  602.         atree_free(tree -> n_child_right);
  603.     }
  604.     reclaim_node(tree);
  605. }
  606.  
  607. /*****************************************************************************
  608.  ****                                                                     ****
  609.  **** (int) atree_eval(tree,vec)                                          ****
  610.  ****                                                                     ****
  611.  **** LPATREE tree;                                                       ****
  612.  **** LPBIT_VEC vec;                                                      ****
  613.  ****                                                                     ****
  614.  **** Synopsis:                                                           ****
  615.  ****                                                                     ****
  616.  **** Applies the _tree_ to the bit vector _vec_ and returns the result,  ****
  617.  **** 1 for true, and 0 for false.                                        ****
  618.  *****************************************************************************/
  619.  
  620. public BOOL FAR PASCAL
  621. atree_eval(tree,vec)
  622.  
  623. LPATREE tree;
  624. LPBIT_VEC vec;
  625.  
  626. {
  627.     register BOOL result;
  628.  
  629.     switch (tree -> c_tag)
  630.     {
  631.     case AND:
  632.         tree -> n_sig_right = UNEVALUATED;
  633. // turn off compiler possibly incorrect assignment warning
  634. #pragma warn -pia
  635.         result = (tree -> n_sig_left =
  636.                      atree_eval(tree -> n_child_left, vec))
  637.               && (tree -> n_sig_right =
  638.                      atree_eval(tree -> n_child_right, vec));
  639. // restore warning state
  640. #pragma warn .pia
  641.         break;
  642.  
  643.     case RIGHT:
  644.         tree -> n_sig_left = UNEVALUATED;
  645.         result = (tree -> n_sig_right =
  646.                      atree_eval(tree -> n_child_right, vec));
  647.         break;
  648.  
  649.     case LEFT:
  650.         tree -> n_sig_right = UNEVALUATED;
  651.         result = (tree -> n_sig_left =
  652.                      atree_eval(tree -> n_child_left, vec));
  653.         break;
  654.  
  655.     case OR:
  656.         tree -> n_sig_right = UNEVALUATED;
  657. // turn off compiler possibly incorrect assignment warning
  658. #pragma warn -pia
  659.         result = (tree -> n_sig_left =
  660.                      atree_eval(tree -> n_child_left, vec))
  661.               || (tree -> n_sig_right =
  662.                      atree_eval(tree -> n_child_right, vec));
  663. // restore warning state
  664. #pragma warn .pia
  665.         break;
  666.  
  667.     case LEAF:
  668.         result = bv_extract((int) tree -> l_bit_no, vec) != tree -> l_comp;
  669.         break;
  670.  
  671.     }
  672.  
  673.     return(result);
  674. }
  675.  
  676. /*****************************************************************************
  677.  ****                                                                     ****
  678.  **** int atree_train(tree,tset,correct_result,bit_col,tset_size,         ****
  679.  ****                    no_correct,epochs,verbosity)                     ****
  680.  ****                                                                     ****
  681.  **** LPATREE tree;                                                       ****
  682.  **** LPBIT_VEC tset;                                                     ****
  683.  **** LPBIT_VEC correct_result;                                           ****
  684.  **** int bit_col;                                                        ****
  685.  **** int tset_size;                                                      ****
  686.  **** int no_correct;                                                     ****
  687.  **** int epochs;                                                         ****
  688.  **** int verbosity;                                                      ****
  689.  ****                                                                     ****
  690.  **** Synopsis:                                                           ****
  691.  ****                                                                     ****
  692.  **** This routine is the heart of the library. It takes an atree _tree_  ****
  693.  **** to be trained, an array of input vectors _tset_, an array of        ****
  694.  **** vectors, _correct_result_ where each bit column holds a correct bit ****
  695.  **** result for each vector in _tset_. [Note: Only a single vector is    ****
  696.  **** actually required here, but doing it this way make life convenient  ****
  697.  **** for training collections of trees for real numbers] An integer      ****
  698.  **** _bit_col_ denoting the column to be trained on. Another integer     ****
  699.  **** _test_size gives the size of both the _tset_ and _correct_result_   ****
  700.  **** arrays.                                                             ****
  701.  ****                                                                     ****
  702.  **** The _tree_ is trained until the number of vectors presented in      ****
  703.  **** _tset_ equals _epoch_ epochs, or the last presentation of the number****
  704.  **** in an epoch had at least _no_correct_ presentations.                ****
  705.  **** The _verbosity_ is currently 0 or 1.                                ****
  706.  **** The routine returns TRUE if it stopped because it succeeded         ****
  707.  **** _no_correct_ times.  Returns FALSE if it did not achieve            ****
  708.  **** _no_correct_.  Returns -1 if aborted.                               ****
  709.  ****                                                                     ****
  710.  *****************************************************************************/
  711.  
  712. #pragma argsused
  713.  
  714. public int FAR PASCAL
  715. atree_train(tree,tset,correct_result,bit_col,tset_size,no_correct,
  716.             epochs,verbosity)
  717.  
  718. LPATREE tree;
  719. LPBIT_VEC tset;
  720. LPBIT_VEC correct_result;
  721. int bit_col;
  722. int tset_size;
  723. int no_correct;
  724. int epochs;
  725. int verbosity;
  726.  
  727. {
  728.     BOOL no_correct_flag = FALSE;
  729.     LPINT vec_list;
  730.     int i;
  731.     int j;
  732.     int cor_this_epoch;
  733.     int vec_num;
  734.     LPBIT_VEC vec;
  735.     static BOOL show_status = TRUE;
  736.  
  737. // verbosity parm has no effect in Windows version
  738.  
  739.     SetDlgItemText(hStatusWnd, IDD_ATREE_EPOCH, "     ");
  740.     SetDlgItemText(hStatusWnd, IDD_ATREE_CORRECT, "     ");
  741.     SetDlgItemText(hStatusWnd, IDD_ATREE_ACTUAL, "     ");
  742.     if(show_status)
  743.     {
  744.         ShowWindow(hStatusWnd, SW_SHOWNOACTIVATE);
  745.     }
  746.     UpdateWindow(hStatusWnd);
  747.  
  748.     vec_list = (LPINT) farmalloc((unsigned) sizeof(int) * tset_size);
  749.     MEMCHECK(vec_list);
  750.  
  751.     for (i = 0; i < tset_size; i++)
  752.     {
  753.         vec_list[i] = i;
  754.     }
  755.  
  756.     /* For the specified number of epochs */
  757.  
  758.     for (i = 0; i < epochs; i++)
  759.     {
  760.         cor_this_epoch = 0;
  761.  
  762.         SetDlgItemInt(hStatusWnd, IDD_ATREE_EPOCH, i, FALSE);
  763.  
  764.         /* Shuffle */
  765.  
  766.         for (j = 0; j < tset_size; j++)
  767.         {
  768.             int a;
  769.             int b;
  770.             int tmp;
  771.  
  772.             a = RANDOM(tset_size);
  773.             do
  774.             {
  775.                 b = RANDOM(tset_size);
  776.             }
  777.             while (a == b);
  778.  
  779.             tmp = vec_list[a];
  780.             vec_list[a] = vec_list[b];
  781.             vec_list[b] = tmp;
  782.         }
  783.  
  784.         /* For the elements of the test set */
  785.  
  786.         for (j = 0; j < tset_size; j++)
  787.         {
  788.             if (atree_quit_flag)
  789.             {
  790.                 atree_quit_flag = FALSE;
  791.                 (void) farfree(vec_list);
  792.                 show_status = ShowWindow(hStatusWnd, SW_HIDE);
  793.                 return(-1);         // exit if requested
  794.             }
  795.  
  796.             /* Pick a random vector */
  797.  
  798.             vec_num = vec_list[j];
  799.             vec = tset + vec_num;
  800.  
  801.             /* Train the tree */
  802.  
  803.             if (train(tree,vec,bv_extract(bit_col,correct_result + vec_num)))
  804.             {
  805.                 /* The tree succeeded */
  806.  
  807.                 cor_this_epoch++;
  808.                 if (cor_this_epoch == no_correct)
  809.                 {
  810.                     no_correct_flag = TRUE;
  811.                     break; /* out of this epoch */
  812.  
  813.                 } /* if (cor_this...) */
  814.             } /* if (train..) */
  815.         } /* for (j = ..) */
  816.  
  817.         SetDlgItemInt(hStatusWnd, IDD_ATREE_CORRECT, cor_this_epoch, FALSE);
  818.  
  819.         /* If no_correct_flag is TRUE here, its time to stop */
  820.  
  821.         if (no_correct_flag || i == epochs - 1)
  822.         {
  823.             int correct = 0;
  824.  
  825.             for (j = 0; j < tset_size; j++)
  826.             {
  827.                 if (atree_eval(tree, tset + j)
  828.                     == bv_extract(bit_col, correct_result + j))
  829.                 {
  830.                     correct++;
  831.                 }
  832.             }
  833.  
  834.             SetDlgItemInt(hStatusWnd, IDD_ATREE_ACTUAL, correct, FALSE);
  835.  
  836.             if (correct >= no_correct)
  837.             {
  838.                 break; /* out of the epoch loop */
  839.             }
  840.         }
  841.     } /* for (i = ...) */
  842.  
  843.     (void) farfree(vec_list);
  844.     show_status = ShowWindow(hStatusWnd, SW_HIDE);
  845.     return(no_correct_flag);
  846. }
  847.  
  848. /*****************************************************************************
  849.  ****                                                                     ****
  850.  **** (void) atree_print(tree,stream, verbosity)                          ****
  851.  ****                                                                     ****
  852.  **** LPATREE tree;                                                       ****
  853.  **** FILE *stream;                                                       ****
  854.  **** int verbosity;                                                      ****
  855.  ****                                                                     ****
  856.  **** Synopsis:                                                           ****
  857.  ****                                                                     ****
  858.  **** Prints out a tree for diagnostic and explanation purposes, the      ****
  859.  **** verbosity levels are 0 or above.                                    ****
  860.  *****************************************************************************/
  861.  
  862. public void FAR PASCAL
  863. atree_print(tree, stream, verbosity)
  864.  
  865. LPATREE tree;
  866. FILE *stream;
  867. int verbosity;
  868.  
  869. {
  870.     /*
  871.      * This routine makes an immediate call to the private
  872.      * print tree routine that takes an extra parameter
  873.      * controlling the indentation.
  874.      */
  875.  
  876.     print_tree(tree,stream,0,verbosity);
  877. }
  878.  
  879.  
  880. /*****************************************************************************
  881.  ****                                                                     ****
  882.  **** LPATREE atree_fold(tree)                                            ****
  883.  ****                                                                     ****
  884.  **** LPATREE tree;                                                       ****
  885.  ****                                                                     ****
  886.  **** Synopsis:                                                           ****
  887.  ****                                                                     ****
  888.  **** This function removes all LEFT and RIGHT nodes from _tree_          ****
  889.  **** and returns a pointer to the resulting tree.                        ****
  890.  ****                                                                     ****
  891.  *****************************************************************************/
  892.  
  893. public LPATREE FAR PASCAL
  894. atree_fold(tree)
  895.  
  896. LPATREE tree;
  897. {
  898.     LPATREE folded_tree;
  899.     int keep;
  900.  
  901.     switch (tree -> c_tag)
  902.     {
  903.     case LEAF:
  904.         folded_tree = tree;
  905.         break;
  906.     case OR:
  907.     case AND:
  908.         tree -> n_child_left = atree_fold(tree -> n_child_left);
  909.         tree -> n_child_right = atree_fold(tree -> n_child_right);
  910.         folded_tree = tree;
  911.         break;
  912.     case LEFT:
  913.     case RIGHT:
  914.         keep = (tree -> c_tag == LEFT) ? LEFT_CHILD : RIGHT_CHILD;
  915.         folded_tree = atree_fold(tree -> n_child[keep]);
  916.         atree_free(tree -> n_child[!keep]);
  917.         reclaim_node(tree);
  918.         break;
  919.     default:
  920.         assert(0);
  921.     }
  922.  
  923.     return(folded_tree);
  924. }
  925.  
  926. /*****************************************************************************
  927.  ****                                                                     ****
  928.  **** LPFAST_TREE atree_compress(tree)                                    ****
  929.  ****                                                                     ****
  930.  **** LPATREE tree;                                                       ****
  931.  ****                                                                     ****
  932.  **** Synopsis:                                                           ****
  933.  ****                                                                     ****
  934.  **** This function converts an atree to a fast_tree.                     ****
  935.  **** See the commentary for the private function                         ****
  936.  **** compress_tree for more information.                                 ****
  937.  ****                                                                     ****
  938.  *****************************************************************************/
  939.  
  940. public LPFAST_TREE FAR PASCAL
  941. atree_compress(tree)
  942. LPATREE tree;
  943. {
  944.     LPFAST_TREE ftree;
  945.     int leaf_num;
  946.     int leaf_count = count_leaves(tree, TRUE);
  947.  
  948.     ftree = (LPFAST_TREE) farmalloc((unsigned) (leaf_count + 1) * sizeof(fast_tree));
  949.     MEMCHECK(ftree);
  950.  
  951.     ftree[leaf_count].bit_no = -1;  /* mark end */
  952.     leaf_num = leaf_count - 1;
  953.     compress_tree(tree, NULL, NULL, ftree, &leaf_num);
  954.  
  955.     return(ftree);
  956. }
  957.  
  958. /*****************************************************************************
  959.  ****                                                                     ****
  960.  **** BOOL atree_fast_eval(ftree, vec)                                    ****
  961.  ****                                                                     ****
  962.  **** LPFAST_TREE ftree;                                                  ****
  963.  **** LPBIT_VEC vec;                                                      ****
  964.  ****                                                                     ****
  965.  **** Synopsis:                                                           ****
  966.  ****                                                                     ****
  967.  **** This function is the fast_tree equivalent of atree_eval.            ****
  968.  ****                                                                     ****
  969.  *****************************************************************************/
  970.  
  971. public BOOL FAR PASCAL
  972. atree_fast_eval(ftree, vec)
  973.  
  974. register LPFAST_TREE ftree;
  975. LPBIT_VEC vec;
  976. {
  977.     register int result;
  978.  
  979.     do
  980.     {
  981.         result = bv_extract(ftree -> bit_no, vec) != ftree -> comp;
  982.     } while ((ftree = ftree -> next[result]) != NULL);
  983.  
  984.     return(result);
  985. }
  986.  
  987.  
  988. /*****************************************************************************
  989.  ****                                                                     ****
  990.  **** void atree_fast_print(ftree, stream)                                ****
  991.  ****                                                                     ****
  992.  **** LPFAST_TREE ftree;                                                  ****
  993.  **** FILE *stream;                                                       ****
  994.  ****                                                                     ****
  995.  **** Synopsis:                                                           ****
  996.  ****                                                                     ****
  997.  **** This function is outputs the fast tree _ftree_ to stream.           ****
  998.  ****                                                                     ****
  999.  *****************************************************************************/
  1000.  
  1001. public void FAR PASCAL
  1002. atree_fast_print(ftree, stream)
  1003.  
  1004. LPFAST_TREE ftree;
  1005. FILE *stream;
  1006. {
  1007.     int i;
  1008.  
  1009.     for (i = 0; ftree[i].bit_no >= 0; i++)
  1010.     {
  1011.         fprintf(stream, "[%3d] bit=%s%d, next[0]=%d, next[1]=%d\n",
  1012.                i, ftree[i].comp ? "!" : "", ftree[i].bit_no,
  1013.                ftree[i].next[0] ? ftree[i].next[0] - ftree : -1,
  1014.                ftree[i].next[1] ? ftree[i].next[1] - ftree : -1);
  1015.     }
  1016. }
  1017.  
  1018.  
  1019. /*****************************************************************************
  1020.  ****                                                                     ****
  1021.  **** int atree_set_code(code, low, high, count, width, dist)             ****
  1022.  ****                                                                     ****
  1023.  **** LPCODE_T code;                                                      ****
  1024.  **** double low;                                                         ****
  1025.  **** double high;                                                        ****
  1026.  **** int count;                                                          ****
  1027.  **** int width;                                                          ****
  1028.  **** int dist;                                                           ****
  1029.  ****                                                                     ****
  1030.  **** Synopsis:                                                           ****
  1031.  ****                                                                     ****
  1032.  **** This is the constructor for type code_t: _code_ is a far pointer    ****
  1033.  **** to a code_t struct, _low_ and _high_ represent the real valued      ****
  1034.  **** boundaries of the encoding, _count_ represents the number of        ****
  1035.  **** vectors in the encoding, _width_ is the number of bits per vector,  ****
  1036.  **** and _dist_ is the number of bits to change between successive       ****
  1037.  **** vectors.                                                            ****
  1038.  **** Returns non-zero on FAILURE.                                        ****
  1039.  ****                                                                     ****
  1040.  *****************************************************************************/
  1041.  
  1042. public int FAR PASCAL
  1043. atree_set_code(code, low, high, count, width, dist)
  1044.  
  1045. LPCODE_T code;
  1046. double low;
  1047. double high;
  1048. int count;
  1049. int width;
  1050. int dist;
  1051. {
  1052.     int error = FALSE;
  1053.  
  1054.     assert(low < high);
  1055.     assert(count > 1);
  1056.     assert(width > 0);
  1057.     assert(dist > 0);
  1058.  
  1059.     code -> width = width;
  1060.     code -> low = low;
  1061.     code -> high = high;
  1062.  
  1063.     if (width == 1)     /* boolean */
  1064.     {
  1065.         code -> vector = (LPBIT_VEC) farmalloc((unsigned) sizeof(bit_vec) * 2);
  1066.         MEMCHECK(code -> vector);
  1067.  
  1068.         // boolean 1
  1069.         code -> vector[0] = *bv_create(1);
  1070.         bv_set(0, &(code -> vector[0]), 0);
  1071.  
  1072.         // boolean 0
  1073.         code -> vector[1] = *bv_create(1);
  1074.         bv_set(0, &(code -> vector[1]), 1);
  1075.  
  1076.         code -> vector_count = 2;
  1077.         code -> step = high - low;
  1078.     }
  1079.     else
  1080.     {
  1081.         if ((code -> vector = atree_rand_walk(count, width, dist)) == NULL)
  1082.         {
  1083.             error = TRUE;
  1084.         }
  1085.         code -> vector_count = count;
  1086.         code -> step = (high - low) / (count - 1);
  1087.     }
  1088.     return(error);
  1089. }
  1090.  
  1091. /*****************************************************************************
  1092.  ****                                                                     ****
  1093.  **** int atree_encode(x, code)                                           ****
  1094.  ****                                                                     ****
  1095.  **** double x;                                                           ****
  1096.  **** LPCODE_T code;                                                      ****
  1097.  ****                                                                     ****
  1098.  **** Synopsis:                                                           ****
  1099.  ****                                                                     ****
  1100.  **** returns the quantization level corresponding to the floating point  ****
  1101.  **** value _x_.  To get the bit vector, use the expression:              ****
  1102.  ****                                                                     ****
  1103.  **** code -> vector + atree_encode(x, code)                              ****
  1104.  ****                                                                     ****
  1105.  *****************************************************************************/
  1106.  
  1107. public int FAR PASCAL
  1108. atree_encode(x, code)
  1109.  
  1110. double x;
  1111. LPCODE_T code;
  1112.  
  1113. {
  1114.     int index;
  1115.  
  1116.     if (code -> width == 1)
  1117.     {
  1118.         index = x > (code -> low + code -> high) / 2;
  1119.     }
  1120.     else if (x < code -> low)
  1121.     {
  1122. //      char szBuffer[100];
  1123.  
  1124. //      (void) sprintf(szBuffer,
  1125. //                     "warning: atree_encode: argument out of range: %f\n", x);
  1126.  
  1127. //      MessageBox(GetDesktopWindow(), szBuffer, "atree_encode()",
  1128. //              MB_ICONHAND | MB_SYSTEMMODAL);
  1129.  
  1130.         index = 0;
  1131.     }
  1132.     else if (x > code -> high)
  1133.     {
  1134. //      char szBuffer[100];
  1135.  
  1136. //      (void) sprintf(szBuffer,
  1137. //                     "warning: atree_encode: argument out of range: %f\n", x);
  1138.  
  1139. //      MessageBox(GetDesktopWindow(), szBuffer, "atree_encode()",
  1140. //              MB_ICONHAND | MB_SYSTEMMODAL);
  1141.  
  1142.         index = code -> vector_count - 1;
  1143.     }
  1144.     else
  1145.     {
  1146.         index = (int) floor(((x - code -> low) / code -> step) + 0.5);
  1147.     }
  1148.  
  1149.     return(index);
  1150. }
  1151.  
  1152.  
  1153. /*****************************************************************************
  1154.  ****                                                                     ****
  1155.  **** int atree_decode(vec, code)                                         ****
  1156.  ****                                                                     ****
  1157.  **** LPBIT_VEC vec;                                                      ****
  1158.  **** LPCODE_T code;                                                      ****
  1159.  ****                                                                     ****
  1160.  **** Synopsis:                                                           ****
  1161.  ****                                                                     ****
  1162.  **** returns the quantization level corresponding to the bit vector      ****
  1163.  **** _vec_.  To get the corresponding floating point value, use the      ****
  1164.  **** expression:                                                         ****
  1165.  ****                                                                     ****
  1166.  **** code -> low + code -> step * atree_decode(vec, code)                ****
  1167.  ****                                                                     ****
  1168.  *****************************************************************************/
  1169.  
  1170. public int FAR PASCAL
  1171. atree_decode(vec, code)
  1172.  
  1173. LPBIT_VEC vec;
  1174. LPCODE_T code;
  1175.  
  1176. {
  1177.     int closest = 0;
  1178.  
  1179.     if (code -> width == 1)     /* boolean */
  1180.     {
  1181.         closest = bv_extract(0, vec);
  1182.     }
  1183.     else
  1184.     {
  1185.         int i;
  1186.         int diff;
  1187.         int closest_bit_diff = code -> width;
  1188.  
  1189.         for (i = 0; i < code -> vector_count; i++)
  1190.         {
  1191.             if ((diff = bv_diff(vec, code -> vector + i)) < closest_bit_diff)
  1192.             {
  1193.                 closest_bit_diff = diff;
  1194.                 closest = i;
  1195.             }
  1196.         }
  1197.     }
  1198.     return(closest);
  1199. }
  1200.  
  1201.  
  1202. /*
  1203.  * atree I/O routines.
  1204.  */
  1205.  
  1206. /*****************************************************************************
  1207.  ****                                                                     ****
  1208.  **** int atree_tree(tree, filename)                                      ****
  1209.  ****                                                                     ****
  1210.  **** LPATREE tree;                                                       ****
  1211.  **** LPSTR filename;                                                     ****
  1212.  ****                                                                     ****
  1213.  **** Synopsis:                                                           ****
  1214.  ****                                                                     ****
  1215.  **** Creates a file "filename", and stores the single tree pointed       ****
  1216.  **** to by _tree_ in that file.                                          ****
  1217.  **** Returns non-zero on failure.                                        ****
  1218.  ****                                                                     ****
  1219.  *****************************************************************************/
  1220.  
  1221. public int FAR PASCAL
  1222. atree_store(tree, filename)
  1223. LPATREE tree;
  1224. LPSTR filename;
  1225. {
  1226.     FILE *fp;
  1227.     char szName[80];
  1228.  
  1229.     lstrcpy(szName, filename);      // fopen doesn't take LPSTR
  1230.  
  1231.     if ((fp = fopen(szName, "w")) == NULL)
  1232.     {
  1233.         return(errno);
  1234.     }
  1235.     atree_write(fp, tree);
  1236.     fclose(fp);
  1237.     return(0);
  1238. }
  1239.  
  1240.  
  1241. /*****************************************************************************
  1242.  ****                                                                     ****
  1243.  **** LPATREE atree_load(filename)                                        ****
  1244.  ****                                                                     ****
  1245.  **** LPSTR filename;                                                     ****
  1246.  ****                                                                     ****
  1247.  **** Synopsis:                                                           ****
  1248.  ****                                                                     ****
  1249.  **** Reads from file "filename", and returns the first tree contained    ****
  1250.  **** in that file.                                                       ****
  1251.  ****                                                                     ****
  1252.  *****************************************************************************/
  1253.  
  1254. public LPATREE FAR PASCAL
  1255. atree_load(filename)
  1256.  
  1257. LPSTR filename;
  1258.  
  1259. {
  1260.     FILE *fp;
  1261.     LPATREE tree;
  1262.     char szName[80];
  1263.  
  1264.     lstrcpy(szName, filename);      // fopen doesn't take LPSTR
  1265.  
  1266.     if ((fp = fopen(szName, "r")) == NULL)
  1267.     {
  1268.         return(NULL);
  1269.     }
  1270.     tree = atree_read(fp);
  1271.     fclose(fp);
  1272.     return(tree);
  1273. }
  1274.  
  1275.  
  1276. /*****************************************************************************
  1277.  ****                                                                     ****
  1278.  **** int atree_write(tree, stream)                                       ****
  1279.  ****                                                                     ****
  1280.  **** LPATREE tree;                                                       ****
  1281.  **** FILE *stream;                                                       ****
  1282.  ****                                                                     ****
  1283.  **** Synopsis:                                                           ****
  1284.  ****                                                                     ****
  1285.  **** Stores a single _tree_ onto _stream_.                               ****
  1286.  **** Returns 0 for success, 1 on failure.                                ****
  1287.  ****                                                                     ****
  1288.  *****************************************************************************/
  1289.  
  1290. public int FAR PASCAL
  1291. atree_write(stream, tree)
  1292.  
  1293. FILE *stream;
  1294. LPATREE tree;
  1295.  
  1296. {
  1297.     return store_tree(tree, stream) || fprintf(stream, ";\n") == EOF;
  1298. }
  1299.  
  1300.  
  1301. /*****************************************************************************
  1302.  ****                                                                     ****
  1303.  **** LPATREE atree_read(stream)                                          ****
  1304.  ****                                                                     ****
  1305.  **** FILE *stream;                                                       ****
  1306.  ****                                                                     ****
  1307.  **** Synopsis:                                                           ****
  1308.  ****                                                                     ****
  1309.  **** Reads tree stored in postfix notation.  Valid symbols are:          ****
  1310.  **** '&', '|', 'L', 'R' (AND, OR, LEFT, and RIGHT respectively),         ****
  1311.  **** and numerals (representing bit numbers) optionally preceded         ****
  1312.  **** by a '!' for negation.  Returns NULL if any error or EOF is         ****
  1313.  **** encountered.  A file may store multiple trees, each tree is         ****
  1314.  **** separated by a ';'.                                                 ****
  1315.  ****                                                                     ****
  1316.  *****************************************************************************/
  1317.  
  1318. public LPATREE FAR PASCAL
  1319. atree_read(stream)
  1320.  
  1321. FILE *stream;
  1322.  
  1323. {
  1324.     token_t t;
  1325.     LPATREE node = NULL;
  1326.     int error = 0;
  1327.  
  1328.     LPATREE stack[STACKSIZE];
  1329.     int top = 0;
  1330. #define ITEMS       top
  1331. #define PUSH(node)  stack[top++] = (node)
  1332. #define POP         stack[--top]
  1333.  
  1334.     while ((error = get_token(stream, &t)) == 0)
  1335.     {
  1336.         if (t.token == EOF || t.token == ';')
  1337.         {
  1338.             break;
  1339.         }
  1340.  
  1341.         if (t.token == LEAF_TOKEN)
  1342.         {
  1343.             node = get_node(LEAF);
  1344.             node -> l_bit_no = t.bit_no;
  1345.             node -> l_comp = t.complemented;
  1346.         }
  1347.         else if (ITEMS < 2)
  1348.         {
  1349.             char szBuffer[80];
  1350.             (void) sprintf(szBuffer,
  1351.                            "atree_read: too few arguments for %c, offset %ld\n",
  1352.                            t.token, ftell(stream));
  1353.  
  1354.             MessageBox(GetDesktopWindow(), szBuffer, "atree_read()",
  1355.                         MB_ICONHAND | MB_SYSTEMMODAL);
  1356.  
  1357.             error++;
  1358.             break;
  1359.         }
  1360.         else
  1361.         {
  1362.             node = get_node(!LEAF);
  1363.             node -> n_cnt_left = (t.token == '|' || t.token == 'L')
  1364.                                  ? MAXSET : MINSET;
  1365.             node -> n_cnt_right = (t.token == '|' || t.token == 'R')
  1366.                                  ? MAXSET : MINSET;
  1367.             node -> c_tag = node_function(node);
  1368.             node -> n_sig_left = UNEVALUATED;
  1369.             node -> n_sig_right = UNEVALUATED;
  1370.             node -> n_child_right = POP;
  1371.             node -> n_child_left = POP;
  1372.         }
  1373.  
  1374.         if (ITEMS >= STACKSIZE)
  1375.         {
  1376.             char szBuffer[80];
  1377.  
  1378.             (void) sprintf(szBuffer, "atree_read: stack overflow\n");
  1379.  
  1380.             MessageBox(GetDesktopWindow(), szBuffer, "atree_read()",
  1381.                         MB_ICONHAND | MB_SYSTEMMODAL);
  1382.  
  1383.             error++;
  1384.             break;
  1385.         }
  1386.         else
  1387.         {
  1388.             PUSH(node);
  1389.         }
  1390.  
  1391.     } /* while */
  1392.  
  1393.     if (!error && ITEMS != 1)
  1394.     {
  1395.         char szBuffer[80];
  1396.  
  1397.         (void) sprintf(szBuffer, "atree_read: unexpected ");
  1398.         if (t.token == EOF)
  1399.         {
  1400.             strcat(szBuffer, "EOF\n");
  1401.         }
  1402.         else
  1403.         {
  1404.             char szErr[80];
  1405.             (void) sprintf(szErr, "';', offset %ld\n", ftell(stream));
  1406.             strcat(szBuffer, szErr);
  1407.         }
  1408.  
  1409.         MessageBox(GetDesktopWindow(), szBuffer, "atree_read()",
  1410.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1411.  
  1412.         error++;
  1413.     }
  1414.  
  1415.     return(error ? NULL : node);
  1416.  
  1417. #undef ITEMS
  1418. #undef PUSH
  1419. #undef POP
  1420. }
  1421.  
  1422. /*
  1423.  * code I/O routines
  1424.  */
  1425.  
  1426. /*****************************************************************************
  1427.  ****                                                                     ****
  1428.  **** int atree_write_code(stream, code)                                  ****
  1429.  ****                                                                     ****
  1430.  **** FILE *stream;                                                       ****
  1431.  **** LPCODE_T code;                                                      ****
  1432.  ****                                                                     ****
  1433.  **** Synopsis:                                                           ****
  1434.  ****                                                                     ****
  1435.  **** Writes _code_ onto _stream_.                                        ****
  1436.  **** Returns 0 for success, 1 on failure.                                ****
  1437.  ****                                                                     ****
  1438.  *****************************************************************************/
  1439.  
  1440. public int FAR PASCAL
  1441. atree_write_code(stream, code)
  1442.  
  1443. FILE *stream;
  1444. LPCODE_T code;
  1445.  
  1446. {
  1447.     int i;
  1448.     int error;
  1449.  
  1450.     error = fprintf(stream, CODING_HEADER_FORMAT,
  1451.                     code -> vector_count, code -> width,
  1452.                     code -> low, code -> high) == EOF;
  1453.  
  1454.     if (!error && code -> width > 1)
  1455.     {
  1456.         for (i = 0; i < code -> vector_count; i++)
  1457.         {
  1458.             if (bv_print(stream, code -> vector + i)
  1459.             || fprintf(stream, "\n") == EOF)
  1460.             {
  1461.                 error = TRUE;
  1462.                 break;
  1463.             }
  1464.         }
  1465.     }
  1466.     return(error);
  1467. }
  1468.  
  1469. /*****************************************************************************
  1470.  ****                                                                     ****
  1471.  **** LPCODE_T atree_read_code(stream)                                    ****
  1472.  ****                                                                     ****
  1473.  **** FILE *stream;                                                       ****
  1474.  **** LPCODE_T code;                                                      ****
  1475.  ****                                                                     ****
  1476.  **** Synopsis:                                                           ****
  1477.  ****                                                                     ****
  1478.  **** Reads a _code_ from _stream_.                                       ****
  1479.  **** Returns NULL if unsuccessful, returns _code_ if successful.         ****
  1480.  ****                                                                     ****
  1481.  *****************************************************************************/
  1482.  
  1483.  
  1484. public LPCODE_T FAR PASCAL
  1485. atree_read_code(stream, code)
  1486.  
  1487. FILE *stream;
  1488. LPCODE_T code;
  1489.  
  1490. {
  1491.     char *buf;
  1492.     char *p;
  1493.     int i;
  1494.     int error = 0;
  1495.     int count, width;
  1496.     float high, low;
  1497.  
  1498.     if (fscanf(stream, CODING_HEADER_FORMAT,
  1499.                &count, &width, &low, &high) != CODING_HEADER_ITEMS)
  1500.     {
  1501.  
  1502.         char szBuffer[80];
  1503.         (void) sprintf(szBuffer, "atree_read_code: bad header, offset %ld\n",
  1504.                        ftell(stream));
  1505.  
  1506.         MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1507.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1508.  
  1509.         return(NULL);
  1510.     }
  1511.     else if (count < 2)
  1512.     {
  1513.         char szBuffer[80];
  1514.  
  1515.         (void) sprintf(szBuffer,
  1516.                        "atree_read_code: vector count too low, offset %ld\n",
  1517.                        ftell(stream));
  1518.  
  1519.         MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1520.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1521.  
  1522.         return(NULL);
  1523.     }
  1524.     else if (high <= low)
  1525.     {
  1526.         char szBuffer[80];
  1527.  
  1528.         (void) sprintf(szBuffer,
  1529.                        "atree_read_code: bad range, offset %ld\n",
  1530.                        ftell(stream));
  1531.  
  1532.         MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1533.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1534.  
  1535.         return(NULL);
  1536.     }
  1537.     else if (width < 1)
  1538.     {
  1539.         char szBuffer[80];
  1540.  
  1541.         (void) sprintf(szBuffer,
  1542.                       "atree_read_code: width must be at least 1, offset %ld\n",
  1543.                       ftell(stream));
  1544.  
  1545.         MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1546.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1547.  
  1548.         return(NULL);
  1549.     }
  1550.  
  1551.     code -> vector_count = count;
  1552.     code -> width = width;
  1553.     code -> low = low;
  1554.     code -> high = high;
  1555.  
  1556.     if (width == 1)
  1557.     {
  1558.         atree_set_code(code, code -> low, /* low */
  1559.                              code -> high, /* high */
  1560.                              2,   /* count */
  1561.                              1,   /* width */
  1562.                              1);  /* distance */
  1563.     }
  1564.     else {
  1565.  
  1566.         code -> step = (code->high - code->low ) / (code -> vector_count - 1);
  1567.         code -> vector = (LPBIT_VEC)
  1568.                     farmalloc((unsigned) sizeof(bit_vec) * code -> vector_count);
  1569.         MEMCHECK(code -> vector);
  1570.  
  1571.         buf = malloc((unsigned) code -> width + 2); /* room for \n and \0 */
  1572.         MEMCHECK(buf);
  1573.  
  1574.         for (i = 0; i < code -> vector_count; i++)
  1575.         {
  1576.             if (fgets(buf, code -> width + 2, stream) == NULL)
  1577.             {
  1578.                 char szBuffer[80];
  1579.  
  1580.                 (void) sprintf(szBuffer,
  1581.                                "atree_read_code: read error on offset %ld\n",
  1582.                                ftell(stream));
  1583.  
  1584.                 MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1585.                             MB_ICONHAND | MB_SYSTEMMODAL);
  1586.  
  1587.                 error++;
  1588.                 break;
  1589.             }
  1590.  
  1591.             if (strlen(buf) != code -> width + 1
  1592.             || buf[code -> width] != '\n')
  1593.             {
  1594.                 char szBuffer[80];
  1595.  
  1596.                 (void) sprintf(szBuffer,
  1597.                           "atree_read_code: inconsistent vector length, offset %ld\n",
  1598.                           ftell(stream));
  1599.  
  1600.                 MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1601.                             MB_ICONHAND | MB_SYSTEMMODAL);
  1602.  
  1603.                 error++;
  1604.                 break;
  1605.             }
  1606.             else
  1607.             {
  1608.                 buf[code -> width] = '\0'; /* remove \n */
  1609.             }
  1610.  
  1611.             if (strspn(buf, "01") != code -> width)
  1612.             {
  1613.                 char szBuffer[80];
  1614.  
  1615.                 (void) sprintf(szBuffer,
  1616.                                "atree_read_code: garbage at offset %ld\n",
  1617.                                ftell(stream));
  1618.  
  1619.                 MessageBox(GetDesktopWindow(), szBuffer, "atree_read_code()",
  1620.                     MB_ICONHAND | MB_SYSTEMMODAL);
  1621.  
  1622.                 error++;
  1623.                 break;
  1624.             }
  1625.  
  1626.             /*
  1627.              * prepare the vector for packing
  1628.              */
  1629.             for (p = buf; *p; p++)
  1630.             {
  1631.                 *p -= '0';
  1632.             }
  1633.             code -> vector[i] = *(bv_pack(buf, code -> width));
  1634.         }
  1635.  
  1636.         (void) farfree(buf);
  1637.         if (error)
  1638.         {
  1639.             (void) farfree(code -> vector);
  1640.             code = NULL;
  1641.         }
  1642.     }
  1643.  
  1644.     return(code);
  1645. }
  1646.  
  1647.  
  1648. /*****************************************************************************
  1649.  *****************************************************************************
  1650.  ****                                                                     ****
  1651.  ****                        Private Routines                             ****
  1652.  ****                                                                     ****
  1653.  *****************************************************************************
  1654.  *****************************************************************************/
  1655.  
  1656. /*
  1657.  * Free list management routines.
  1658.  */
  1659. static LPATREE_LEAF free_leaf_list = NULL;
  1660. static LPATREE_NODE free_node_list = NULL;
  1661.  
  1662. #define get_free_list(type, free_list) { \
  1663.   int i; \
  1664.   type far *ptr = (type far *) farmalloc(sizeof(type) * NEWMALLOC); \
  1665.   MEMCHECK(ptr); \
  1666.   for (i = 0; i < NEWMALLOC - 1; i++) \
  1667.     ptr[i].next = &ptr[i + 1]; \
  1668.   ptr[NEWMALLOC - 1].next = free_list; \
  1669.   free_list = ptr; \
  1670. }
  1671.  
  1672. private LPATREE NEAR PASCAL
  1673. get_node(tag)
  1674.  
  1675. int tag;
  1676.  
  1677. {
  1678.     LPATREE node;
  1679.  
  1680.     if (tag == LEAF)
  1681.     {
  1682.  
  1683.         /*
  1684.          * add to free_leaf_list if necessary.
  1685.          */
  1686.         if (free_leaf_list == NULL)
  1687.         {
  1688.             get_free_list(atree_leaf, free_leaf_list);
  1689.         }
  1690.  
  1691.         node = (LPATREE) free_leaf_list;
  1692.         free_leaf_list = free_leaf_list -> next;
  1693.     }
  1694.     else {
  1695.  
  1696.         /*
  1697.          * add to free_node_list if necessary.
  1698.          */
  1699.         if (free_node_list == NULL)
  1700.         {
  1701.             get_free_list(atree_node, free_node_list);
  1702.         }
  1703.  
  1704.         node = (LPATREE) free_node_list;
  1705.         free_node_list = free_node_list -> next;
  1706.     }
  1707.  
  1708.     node -> c_tag = tag;
  1709.     return(node);
  1710. }
  1711. #undef get_free_list
  1712.  
  1713. /*
  1714.  * function reclaim_node()
  1715.  *
  1716.  * returns a node to its appropriate free_list
  1717.  */
  1718.  
  1719. private void NEAR PASCAL
  1720. reclaim_node(tree)
  1721.  
  1722. LPATREE tree;
  1723.  
  1724. {
  1725.     if (tree -> c_tag == LEAF)
  1726.     {
  1727.         tree -> leaf.next = free_leaf_list;
  1728.         free_leaf_list = (LPATREE_LEAF) tree;
  1729.     }
  1730.     else
  1731.     {
  1732.         tree -> node.next = free_node_list;
  1733.         free_node_list = (LPATREE_NODE) tree;
  1734.     }
  1735. }
  1736.  
  1737. /*
  1738.  * This routine recursively creates a random tree in the previously allocated
  1739.  * space starting at _tree_. It returns a pointer giving the next available
  1740.  * space for other calls.
  1741.  */
  1742.  
  1743. private LPATREE NEAR PASCAL
  1744. build_tree(connection, complemented, start, end)
  1745.  
  1746. LPINT connection;
  1747. BOOL far *complemented;
  1748. int start;
  1749. int end;
  1750. {
  1751.     LPATREE node;
  1752.     int mid;
  1753.  
  1754.     /* Are we at a leaf? */
  1755.  
  1756.     if (start == end)
  1757.     {
  1758.         node = get_node(LEAF);
  1759.         node -> l_comp = complemented[start];
  1760.         node -> l_bit_no = connection[start];
  1761.     }
  1762.     else
  1763.     {
  1764.         /* This is a node. */
  1765.  
  1766.         node = get_node(AND);
  1767.         node -> c_tag = RANDOM(4);
  1768.  
  1769.         node -> n_cnt_left =
  1770.           (node -> c_tag == LEFT || node -> c_tag == OR) ? ABOVEMID : BELOWMID;
  1771.         node -> n_cnt_right =
  1772.           (node -> c_tag == RIGHT || node -> c_tag == OR) ? ABOVEMID : BELOWMID;
  1773.  
  1774.         /* clear the signals */
  1775.  
  1776.         node -> n_sig_right = UNEVALUATED;
  1777.         node -> n_sig_left = UNEVALUATED;
  1778.  
  1779.         /* Create descendants */
  1780.  
  1781.         mid = start + ((end - start)/2);
  1782.         node -> n_child_left
  1783.            = build_tree(connection, complemented, start, mid);
  1784.         node -> n_child_right
  1785.            = build_tree(connection, complemented, mid+1, end);
  1786.     }
  1787.     return(node);
  1788. }
  1789.  
  1790. /*
  1791.  * print_tree routine prints out an atree to the
  1792.  * file pointed to by _stream_
  1793.  */
  1794.  
  1795. private void NEAR PASCAL
  1796. print_tree(tree, stream, indent,verbosity)
  1797.  
  1798. LPATREE tree;
  1799. FILE *stream;
  1800. int indent;
  1801. int verbosity;
  1802.  
  1803. {
  1804.     int i;
  1805.  
  1806.     if (tree -> c_tag != LEAF)
  1807.     {
  1808.         print_tree(tree -> n_child_right, stream, indent + 3, verbosity);
  1809.     }
  1810.  
  1811.     for (i = 0; i < indent; i++)
  1812.     {
  1813.         fprintf(stream, " ");
  1814.     }
  1815.  
  1816.     switch (tree -> c_tag)
  1817.     {
  1818.     case AND:
  1819.         fprintf(stream, "AND\n");
  1820.         break;
  1821.  
  1822.     case LEFT:
  1823.         fprintf(stream, "LEFT\n");
  1824.         break;
  1825.  
  1826.     case RIGHT:
  1827.         fprintf(stream, "RIGHT\n");
  1828.         break;
  1829.  
  1830.     case OR:
  1831.         fprintf(stream, "OR\n");
  1832.         break;
  1833.  
  1834.     case LEAF:
  1835.         fprintf(stream, "%sLEAF : %d\n",
  1836.                tree -> l_comp ? "~" : "", tree -> l_bit_no);
  1837.         break;
  1838.     }
  1839.  
  1840.     if (tree -> c_tag != LEAF)
  1841.     {
  1842.        print_tree(tree -> n_child_left, stream, indent + 3, verbosity);
  1843.     }
  1844. }
  1845.  
  1846. /*
  1847.  * This routine is actually responsible for the training of a tree for a
  1848.  * single input vector and desired result. If the tree gets the correct result
  1849.  * before the adaptation step occurs, the routine returns TRUE, otherwise,
  1850.  * false.
  1851.  */
  1852.  
  1853. private BOOL NEAR PASCAL
  1854. train(tree,vec,desired)
  1855.  
  1856. LPATREE tree;
  1857. LPBIT_VEC vec;
  1858. BOOL desired;
  1859.  
  1860. {
  1861.     BOOL correct;
  1862.  
  1863.     (void) atree_eval(tree,vec);
  1864.  
  1865.     adapt(tree,vec,desired);
  1866.  
  1867.     correct = atree_eval(tree,vec) == desired;
  1868.  
  1869.     if (!correct)
  1870.     {
  1871.         adapt(tree,vec,desired);
  1872.     }
  1873.  
  1874.     return(correct);
  1875. }
  1876.  
  1877. private void NEAR PASCAL
  1878. adapt(tree,vec,desired)
  1879.  
  1880. LPATREE tree;
  1881. LPBIT_VEC vec;
  1882. BOOL desired;
  1883.  
  1884. {
  1885.     register int lres;
  1886.     register int rres;
  1887.     register int funct;
  1888.  
  1889. /*
  1890.  * INCR and DECR implement bounded counters.
  1891.  */
  1892. #define INCR(t) ((t) += ((t) < MAXSET))
  1893. #define DECR(t) ((t) -= ((t) > MINSET))
  1894.  
  1895.     Windows_Interrupt(200);
  1896.  
  1897.     funct = tree -> c_tag;
  1898.  
  1899.     if (funct != LEAF)
  1900.     {
  1901.         /* If the left child is unevaluated, evaluate it */
  1902.  
  1903.         if ((lres = tree -> n_sig_left) == UNEVALUATED)
  1904.         {
  1905.             lres = atree_eval(tree -> n_child_left, vec);
  1906.             tree -> n_sig_left = lres;
  1907.         }
  1908.  
  1909.         /* If the right child is unevaluated, evaluate it */
  1910.  
  1911.         if ((rres = tree -> n_sig_right) == UNEVALUATED)
  1912.         {
  1913.             rres = atree_eval(tree -> n_child_right, vec);
  1914.             tree -> n_sig_right = rres;
  1915.         }
  1916.  
  1917.         /* Update the counters if needed */
  1918.  
  1919.         if (lres != rres)
  1920.         {
  1921.             if (lres)
  1922.             {
  1923.                 (void) (desired ? INCR(tree -> n_cnt_left)
  1924.                                 : DECR(tree -> n_cnt_left));
  1925.             }
  1926.             else
  1927.             {
  1928.                 (void) (desired ? INCR(tree -> n_cnt_right)
  1929.                                 : DECR(tree -> n_cnt_right));
  1930.             }
  1931.  
  1932.             /* has the node function changed? */
  1933.  
  1934.             tree -> c_tag = node_function(tree);
  1935.             funct = tree -> c_tag;
  1936.         }
  1937.  
  1938.         /* Assign responsibility to the left child */
  1939.  
  1940.         if (rres != desired || funct != (rres ? OR : AND))
  1941.         {
  1942.             adapt(tree -> n_child_left, vec, desired);
  1943.         }
  1944.  
  1945.         /* Assign responsibility to the right child */
  1946.  
  1947.         if (lres != desired || funct != (lres ? OR : AND))
  1948.         {
  1949.             adapt(tree -> n_child_right, vec, desired);
  1950.         }
  1951.     }
  1952. #undef INCR
  1953. #undef DECR
  1954. }
  1955.  
  1956. private int NEAR PASCAL
  1957. node_function(tree)
  1958.  
  1959. LPATREE tree;
  1960.  
  1961. {
  1962.     int result;
  1963.  
  1964.     if ((tree -> n_cnt_left) >= ABOVEMID)
  1965.     {
  1966.         result = (tree -> n_cnt_right >= ABOVEMID) ? OR : LEFT;
  1967.     }
  1968.     else
  1969.     {
  1970.         result = (tree -> n_cnt_right >= ABOVEMID) ? RIGHT : AND;
  1971.     }
  1972.  
  1973.     return(result);
  1974. }
  1975.  
  1976. /*
  1977.  * compress_tree:
  1978.  *   Alters the respresentation of an atree into a fast_tree.
  1979.  * A fast_tree is essentially a list of leaves; each leaf in the
  1980.  * list contains two pointers to subsequent leaves to evaluate,
  1981.  * one for each possible result of evaluating the current leaf.
  1982.  * A next pointer of NULL indicates that the evaluation is complete,
  1983.  * and the result of the tree is the result of the current leaf.
  1984.  *
  1985.  * parameters:
  1986.  *   'next_if_0' and 'next_if_1' each hold the location of the
  1987.  * next leaf to evaluate if the value of the current 'node' is
  1988.  * known.  Of course, for the root these are NULL.  'leaf_num' is the
  1989.  * current index into 'ftree'; it starts at the last leaf.
  1990.  *
  1991.  * notes:
  1992.  *   For non-leaf nodes, we traverse the children in reverse order
  1993.  * because we need to know the first leaf of a node's sibling (this
  1994.  * is the next leaf to evaluate if any children of 'node' produce a
  1995.  * tag value).  If we go backwards, we know that this is the last
  1996.  * leaf we visited.
  1997.  */
  1998.  
  1999. private void NEAR PASCAL
  2000. compress_tree(node, next_if_0, next_if_1, ftree, leaf_num)
  2001. LPATREE node;
  2002. LPFAST_TREE next_if_0;
  2003. LPFAST_TREE next_if_1;
  2004. LPFAST_TREE ftree;
  2005. LPINT leaf_num;
  2006. {
  2007.  
  2008.     assert(*leaf_num >= 0);
  2009.     switch (node -> c_tag)
  2010.     {
  2011.     case LEAF:
  2012.         ftree[*leaf_num].next[0] = next_if_0;
  2013.         ftree[*leaf_num].next[1] = next_if_1;
  2014.         ftree[*leaf_num].bit_no = node -> l_bit_no;
  2015.         ftree[*leaf_num].comp = node -> l_comp;
  2016.         (*leaf_num)--;
  2017.         break;
  2018.     case AND:
  2019.         compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num);
  2020.         compress_tree(node->n_child[0], next_if_0, &ftree[*leaf_num+1], ftree,
  2021.                       leaf_num);
  2022.         break;
  2023.     case OR:
  2024.         compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num);
  2025.         compress_tree(node->n_child[0], &ftree[*leaf_num+1], next_if_1, ftree,
  2026.                       leaf_num);
  2027.         break;
  2028.     case LEFT:
  2029.         compress_tree(node->n_child[0], next_if_0, next_if_1, ftree, leaf_num);
  2030.         break;
  2031.     case RIGHT:
  2032.         compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num);
  2033.         break;
  2034.     default:
  2035.         assert(0);
  2036.     }
  2037. }
  2038.  
  2039. private int NEAR PASCAL
  2040. count_leaves(tree, fold)
  2041. LPATREE tree;
  2042. int fold;
  2043. {
  2044.     if (tree -> c_tag == LEAF)
  2045.     {
  2046.         return 1;
  2047.     }
  2048.     else if (fold && tree -> c_tag == LEFT)
  2049.     {
  2050.         return count_leaves(tree -> n_child_left, fold);
  2051.     }
  2052.     else if (fold && tree -> c_tag == RIGHT)
  2053.     {
  2054.         return count_leaves(tree -> n_child_right, fold);
  2055.     }
  2056.     else
  2057.     {
  2058.         return count_leaves(tree -> n_child_left, fold)
  2059.              + count_leaves(tree -> n_child_right, fold);
  2060.     }
  2061. }
  2062.  
  2063. /*
  2064.  * function: store_tree
  2065.  *
  2066.  * Stores _tree_ onto _stream_ using postfix notation.
  2067.  * Returns non-zero on failure.
  2068.  */
  2069. private int NEAR PASCAL
  2070. store_tree(tree, stream)
  2071. LPATREE tree;
  2072. FILE *stream;
  2073. {
  2074.     int error;
  2075.  
  2076.     if (tree -> c_tag == LEAF)
  2077.     {
  2078.         error = fprintf(stream, "%s%d ",
  2079.                         tree -> l_comp ? "!" : "", tree -> l_bit_no) == EOF;
  2080.     }
  2081.     else
  2082.     {
  2083.         error = store_tree(tree -> n_child_left, stream)
  2084.              || store_tree(tree -> n_child_right, stream);
  2085.         if (!error)
  2086.         {
  2087.             switch (tree -> c_tag)
  2088.             {
  2089.             case AND:
  2090.                 error = fprintf(stream, "&") == EOF;
  2091.                 break;
  2092.             case OR:
  2093.                 error = fprintf(stream, "|") == EOF;
  2094.                 break;
  2095.             case LEFT:
  2096.                 error = fprintf(stream, "L") == EOF;
  2097.                 break;
  2098.             case RIGHT:
  2099.                 error = fprintf(stream, "R") == EOF;
  2100.                 break;
  2101.             }
  2102.         }
  2103.     }
  2104.     return(error);
  2105. }
  2106.  
  2107. /*
  2108.  * function: get_token
  2109.  *
  2110.  * Reads the next token from _stream_ and returns information about it
  2111.  * in _t_.  Returns 0 for success, 1 for failure.
  2112.  */
  2113. private int NEAR PASCAL
  2114. get_token(stream, t)
  2115. FILE *stream;
  2116. token_t far *t;
  2117. {
  2118.     int c;
  2119.  
  2120.     /* skip white space */
  2121.     while (isspace(c = getc(stream)))
  2122.        ;
  2123.  
  2124.     t -> complemented = 0;
  2125.     switch (c)
  2126.     {
  2127.     case EOF:
  2128.     case 'L':
  2129.     case 'R':
  2130.     case '&':
  2131.     case '|':
  2132.     case ';':
  2133.         t -> token = c;
  2134.       break;
  2135.     case '!':
  2136.         t -> complemented = 1;
  2137.         /* skip white space */
  2138.         while (isspace(c = getc(stream)))
  2139.            ;
  2140.  
  2141.         if (!isdigit(c))
  2142.         {
  2143.             char szBuffer[80];
  2144.  
  2145.             (void) sprintf(szBuffer,
  2146.                            "get_token: expecting digit after '!', offset %ld\n",
  2147.                            ftell(stream));
  2148.  
  2149.             MessageBox(GetDesktopWindow(), szBuffer, "get_token()",
  2150.                         MB_ICONHAND | MB_SYSTEMMODAL);
  2151.  
  2152.             return(1);
  2153.         }
  2154.         /* FALLTHRU */
  2155.  
  2156.     case '0': case '1': case '2': case '3': case '4':
  2157.     case '5': case '6': case '7': case '8': case '9':
  2158.         t -> token = LEAF_TOKEN;
  2159.         t -> bit_no = c - '0';
  2160.         while (isdigit(c = getc(stream)))
  2161.         {
  2162.             t -> bit_no = t -> bit_no * 10 + c - '0';
  2163.         }
  2164.         (void) ungetc(c, stream);
  2165.         break;
  2166.  
  2167.     default:
  2168.         {
  2169.             char szBuffer[80];
  2170.  
  2171.             (void) sprintf(szBuffer,
  2172.                            "get_token: unexpected symbol: '%c', offset %ld\n",
  2173.                            c, ftell(stream));
  2174.  
  2175.             MessageBox(GetDesktopWindow(), szBuffer, "get_token()",
  2176.                         MB_ICONHAND | MB_SYSTEMMODAL);
  2177.  
  2178.             return(1);
  2179.         }
  2180.     }
  2181.  
  2182.     return(0);
  2183. }
  2184.